package sorting;

import java.util.Arrays;

import util.ArrayUtil;
import util.MathUtil;

public class QuickSortWithEqual {
	public static void sort(float[] numbers, int l, int r)
	{
		if(l >= r) return;

		if(r - l > 1)
			ArrayUtil.each(numbers, r, MathUtil.random(l, r));

		Tag tag = partition(numbers, l, r);
		
		if(tag.getEl() > l)
			sort(numbers, l, tag.getEl() - 1);
		
		if(tag.getEr() < r)
			sort(numbers, tag.getEr() + 1, r);
	}
	
	private static Tag partition(float[] numbers, int l, int r)
	{
		float pivotValue = numbers[r];
		int el = l;
		int er = r;
		int i = l;
		while(i <= er)
		{
			float v = numbers[i];
			if(v < pivotValue)
			{
				ArrayUtil.each(numbers, i, el ++);
				i ++;
			}
			else if(v > pivotValue)
			{
				ArrayUtil.each(numbers, i, er --);
			}
			else 
			{
				i ++;
			}
		}

		return new Tag(el, er);
	}
	
	public static void main(String[] args) {
		float[] numbers = {1, 4, 2, 7, 8, 3, 5, 6, 10, 9, 10, 8, 3};
		sort(numbers, 0, numbers.length - 1);
		
		System.out.println(Arrays.toString(numbers));
	}
}

class Tag
{
	private int el;
	private int er;
	public Tag(int el, int er) {
		this.el = el;
		this.er = er;
	}
	
	public int getEl() {
		return el;
	}
	
	public int getEr() {
		return er;
	}
}
